def numIslands(grid):
    """
    :type grid: List[List[str]]
    :rtype: int
    """
    if grid == None or len(grid) == 0:
        return 0
    res = 0
    row = len(grid)
    col = len(grid[0])
    for i in range(row):
        for j in range(col):
            if grid[i][j] == '1':
                res += 1
                # 找到岛屿后，将岛屿的1同化成0(水平/竖直)，这样就不会重复找到该岛屿
                dfs(grid, i, j, row, col)
    return res


def dfs(grid, x, y, row, col):
    # 超出网格或者原本为0 则停止同化
    if x < 0 or y < 0 or x >= row or y >= col or grid[x][y] == '0':
        return
    grid[x][y] = '0'
    # 上下左右四个方向分别同化
    dfs(grid, x + 1, y, row, col)
    dfs(grid, x - 1, y, row, col)
    dfs(grid, x, y + 1, row, col)
    dfs(grid, x, y - 1, row, col)


grid = [["1", "1", "1"], ["0", "1", "0"], ["1", "1", "1"]]
print(numIslands(grid))
